/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

struct TreeNode
{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

#define MAX_SIZE 200
#define TRUE 1
#define FALSE 0
// 判断条件
bool judge(struct TreeNode *left, struct TreeNode *right)
{
    // 如果两个节点都为空，则也表示队列相等
    if ((left == NULL) && (right == NULL))
    {
        return TRUE;
    }
    // 1个为空，另一个不为空则不相等
    if ((left == NULL) || (right == NULL))
    {
        return FALSE;
    }
    // 两个都不为空则且值不相等则为不相等
    if (left->val != right->val)
    {
        return FALSE;
    }

    return TRUE;
}

bool isSymmetric(struct TreeNode *root)
{
    // 队列是否为空
    if (root == NULL)
    {
        return TRUE;
    }
    // 只有一个根节点，为对称
    if ((root->left == NULL) && (root->right == NULL))
    {
        return TRUE;
    }
    // 只有一个左孩子或右孩子，非对称
    if ((root->left == NULL) || (root->right == NULL))
    {
        return FALSE;
    }
    // 初始化队列
    struct TreeNode *leftq[MAX_SIZE];
    struct TreeNode *rightq[MAX_SIZE];
    struct TreeNode *q1;
    struct TreeNode *q2;
    int head1 = -1;
    int tail1 = -1;
    int head2 = -1;
    int tail2 = -1;
    // BFS初始化压入队列种子
    // 将左孩子和右孩子分别压入到各自队列
    leftq[++tail1] = root->left;
    rightq[++tail2] = root->right;

    // BFS标准循环
    while (head1 < tail1)
    {
        // 取出各自队列top
        q1 = leftq[++head1];
        q2 = rightq[++head2];
        // 一旦不满足则直接跳出BFS循环
        if (judge(q1, q2) == FALSE)
        {
            return FALSE;
        }
        // 需要判断是否为空节点，添加后续的左右孩子
        if (q1 != NULL)
        {
            /*
            将left的left节点和right的right节点放入队列
            将left的right节点和right的left节点放入队列
            */
            // 左左 和 右右 下回取出来一起比
            leftq[++tail1] = q1->left;
            rightq[++tail2] = q2->right;
            // 左右 和 右左 下回取出来一起比
            leftq[++tail1] = q1->right;
            rightq[++tail2] = q2->left;
        }
    }

    // 循环一直比对结束，则为对称二叉树
    return TRUE;
}